The matching extendability of 7-connected maximal 1-plane graphs.

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. A graph is said to be \(k(\geq 1)\)-extendable if every matching of size \(k(\geq 1)\) can be extended to a perfect matching. It is known that the vertex connectivity of a 1plane graph is at most 7. In this paper, we characterize the k-extendability of 7connected maximal 1-plane graphs. We show that every 7 -connected maximal 1 plane graph with even order is k-extendable for \(1 \leq k \leq 3\). And any 7-connected maximal 1 -plane graph is not k -extendable for \(4 \leq k \leq 11\). As for \(k \geq 12\), any 7 connected maximal 1-plane graph with $n$ vertices is not $k$-extendable unless \(\mathrm{n}=2 \mathrm{k}\).

Recommended citation: Y. Huang, L. Zhang and Y. Wang, The matching extendability of 7-connected maximal 1-plane graphs, Discuss. Math. Graph Theory 44(2024), no.~2, 777--790; MR4715705
Download Paper | Download Slides